#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class KN_Square {
public:
    int superEggDrop(int K, int N) {
        int dp[K + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            dp[1][i] = i;
            dp[0][i] = 0;
        }
        for (int i = 0; i <= K; i++)
            dp[i][0] = 0;
        
        for (int k = 2; k <= K; k++) {
            for (int n = 1; n <= N; n++) {
                int theMinDrop = INT_MAX;
                for (int x = 1; x <= n; x++)
                    theMinDrop = min(theMinDrop, 1 + max(dp[k - 1][x - 1], dp[k][n - x]));
                dp[k][n] = theMinDrop;
            }
        }

        return dp[K][N];
    }
};

class KNlogN {
public:
    int superEggDrop(int K, int N) {
        int dp[K + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            dp[1][i] = i;
            dp[0][i] = 0;
        }
        for (int i = 0; i <= K; i++)
            dp[i][0] = 0;
        
        for (int k = 2; k <= K; k++) {
            for (int n = 1; n <= N; n++) {
                int low = 1, high = n;
                // 二分查找模版
                while (low < high) {
                    int mid = low + (high - low) / 2;
                    int broken = dp[k - 1][mid - 1];
                    int not_broken = dp[k][n - mid];

                    if (broken < not_broken)
                        low = mid + 1;
                    else
                        high = mid;
                }
                dp[k][n] = 1 + max(dp[k - 1][low - 1], dp[k][n - low]);
            }
        }

        return dp[K][N];
    }
};

// 重定义dp数组，dp[k][m] = n ==> 对于k个鸡蛋，在扔m次的情况下，最多可以得到检验n层大楼的答案
class KN {
    // 平均时间复杂度O(KlogN)
public:
    int superEggDrop(int K, int N) {
        int dp[K + 1][N + 1];
        for (int i = 1; i <= N; i++)
            dp[0][i] = 0;
        for (int i = 0; i <= K; i++)
            dp[i][0] = 0;
        
        int m = 0;
        while (dp[K][m] < N) {
            m++;
            for (int k = 1; k <= K; k++)
                dp[k][m] = 1 + dp[k - 1][m - 1] + dp[k][m - 1];
        }

        return m;
    }
};